A characterization of alternating log time by ramified recurrence
Identifieur interne : 009D70 ( Main/Exploration ); précédent : 009D69; suivant : 009D71A characterization of alternating log time by ramified recurrence
Auteurs : Daniel Leivant [États-Unis] ; Jean-Yves Marion [États-Unis, France]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 2000.
Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Simulation.
- mix :
English descriptors
- KwdEn :
- Teeft :
- Action state, Algebra, Alogtime, Base case, Basic tree operations, Binary, Binary trees, Bitwise, Bitwise computable, Coercion function, Complexity classes, Computable, Computation, Computation tree, Computational, Computational complexity, Computer science, Constant number, Constant time, Corresponding author, Elsevier science, Fbit, Feasible mathematics, Free algebra, Free algebras, Function readlt, Functions bitwise computable, Higher order, Immediate subtrees, Initial functions, Input tape, Lecture notes, Leivant, Linear recurrence, List representation, Logarithmic time, Lrrs, Main result, Marion, Mathematical logic, Monotonic recurrence, Nite computation tree, Nite model theory, Numeral, Numeric value, Operational semantics, Parameter substitution, Programming languages, Reading bits, Reading state, Readlt, Readnl, Recurrence, Recurrence argument, Recurrence schema, Recursion, Relevant cases, Root address, Schema, Singleton tree, Straightforward induction, Substitution, Substitution functions, Terminal states, Transition table, Unary, Unary numerals, Uniform variant, Work stack.
Abstract
Abstract: We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the UE∗-uniform variant of NC1 Ruzzo, J. Comput. System Sci. 22 (1981) 365–383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.
Url:
DOI: 10.1016/S0304-3975(99)00209-1
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001D76
- to stream Istex, to step Curation: 001D53
- to stream Istex, to step Checkpoint: 002023
- to stream Main, to step Merge: 00A351
- to stream Hal, to step Corpus: 000590
- to stream Hal, to step Curation: 000590
- to stream Hal, to step Checkpoint: 006332
- to stream Main, to step Merge: 00A962
- to stream PascalFrancis, to step Corpus: 000A51
- to stream PascalFrancis, to step Curation: 000031
- to stream PascalFrancis, to step Checkpoint: 000A34
- to stream Main, to step Merge: 00A640
- to stream Main, to step Curation: 009D70
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>A characterization of alternating log time by ramified recurrence</title><author><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name></author><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:802489BC4207A667F96797D445C420ABC96B0711</idno><date when="2000" year="2000">2000</date><idno type="doi">10.1016/S0304-3975(99)00209-1</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-3NK033P5-P/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001D76</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001D76</idno><idno type="wicri:Area/Istex/Curation">001D53</idno><idno type="wicri:Area/Istex/Checkpoint">002023</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002023</idno><idno type="wicri:doubleKey">0304-3975:2000:Leivant D:a:characterization:of</idno><idno type="wicri:Area/Main/Merge">00A351</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00099078</idno><idno type="url">https://hal.inria.fr/inria-00099078</idno><idno type="wicri:Area/Hal/Corpus">000590</idno><idno type="wicri:Area/Hal/Curation">000590</idno><idno type="wicri:Area/Hal/Checkpoint">006332</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">006332</idno><idno type="wicri:doubleKey">0304-3975:2000:Leivant D:a:characterization:of</idno><idno type="wicri:Area/Main/Merge">00A962</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:00-0264081</idno><idno type="wicri:Area/PascalFrancis/Corpus">000A51</idno><idno type="wicri:Area/PascalFrancis/Curation">000031</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000A34</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A34</idno><idno type="wicri:doubleKey">0304-3975:2000:Leivant D:a:characterization:of</idno><idno type="wicri:Area/Main/Merge">00A640</idno><idno type="wicri:Area/Main/Curation">009D70</idno><idno type="wicri:Area/Main/Exploration">009D70</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">A characterization of alternating log time by ramified recurrence</title><author><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computer Science Department, Indiana University, Bloomington, IN 47405</wicri:regionArea><placeName><region type="state">Indiana</region></placeName></affiliation></author><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Université Nancy 2, Loria, Projet Calligramme, B.P. 239, Campus Scientifique, 54506 Vandœuvre-lès-Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName><orgName type="university">Université Nancy 2</orgName></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2000">2000</date><biblScope unit="volume">236</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="193">193</biblScope><biblScope unit="page" to="208">208</biblScope></imprint><idno type="ISSN">0304-3975</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Binary tree</term><term>Branching</term><term>Computational complexity</term><term>Recurrence</term><term>Recursion</term><term>Simulation</term><term>Substitution</term><term>Tree recursion</term><term>Tree(graph)</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Arbre binaire</term><term>Arbre graphe</term><term>Complexité calcul</term><term>Ramification</term><term>Récurrence</term><term>Récursion</term><term>Récursion arbre</term><term>Simulation</term><term>Substitution</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Action state</term><term>Algebra</term><term>Alogtime</term><term>Base case</term><term>Basic tree operations</term><term>Binary</term><term>Binary trees</term><term>Bitwise</term><term>Bitwise computable</term><term>Coercion function</term><term>Complexity classes</term><term>Computable</term><term>Computation</term><term>Computation tree</term><term>Computational</term><term>Computational complexity</term><term>Computer science</term><term>Constant number</term><term>Constant time</term><term>Corresponding author</term><term>Elsevier science</term><term>Fbit</term><term>Feasible mathematics</term><term>Free algebra</term><term>Free algebras</term><term>Function readlt</term><term>Functions bitwise computable</term><term>Higher order</term><term>Immediate subtrees</term><term>Initial functions</term><term>Input tape</term><term>Lecture notes</term><term>Leivant</term><term>Linear recurrence</term><term>List representation</term><term>Logarithmic time</term><term>Lrrs</term><term>Main result</term><term>Marion</term><term>Mathematical logic</term><term>Monotonic recurrence</term><term>Nite computation tree</term><term>Nite model theory</term><term>Numeral</term><term>Numeric value</term><term>Operational semantics</term><term>Parameter substitution</term><term>Programming languages</term><term>Reading bits</term><term>Reading state</term><term>Readlt</term><term>Readnl</term><term>Recurrence</term><term>Recurrence argument</term><term>Recurrence schema</term><term>Recursion</term><term>Relevant cases</term><term>Root address</term><term>Schema</term><term>Singleton tree</term><term>Straightforward induction</term><term>Substitution</term><term>Substitution functions</term><term>Terminal states</term><term>Transition table</term><term>Unary</term><term>Unary numerals</term><term>Uniform variant</term><term>Work stack</term></keywords><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Simulation</term></keywords><keywords scheme="mix" xml:lang="fr"><term>complexité de récursion</term><term>recursion complexity</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the UE∗-uniform variant of NC1 Ruzzo, J. Comput. System Sci. 22 (1981) 365–383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence.</div></front></TEI><affiliations><list><country><li>France</li><li>États-Unis</li></country><region><li>Grand Est</li><li>Indiana</li><li>Lorraine (région)</li></region><settlement><li>Vandœuvre-lès-Nancy</li></settlement><orgName><li>Université Nancy 2</li></orgName></list><tree><country name="États-Unis"><noRegion><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name></noRegion><name sortKey="Leivant, Daniel" sort="Leivant, Daniel" uniqKey="Leivant D" first="Daniel" last="Leivant">Daniel Leivant</name><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></country><country name="France"><region name="Grand Est"><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 009D70 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 009D70 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:802489BC4207A667F96797D445C420ABC96B0711
|texte= A characterization of alternating log time by ramified recurrence
}}
| This area was generated with Dilib version V0.6.33. |  |